package q05_LongestPalindrome;

public class Solution {
    /**
     * 最长回文字符子串的寻找，该方法是使用中心扩散法来解决该问题
     * 首先建立一个方法，该方法从两个字符开始(可以是同一个位置)然后向两边扩散，确认该位置向左一个字符和向右一个字符相同
     * 然后循环到不相同位置，得到左右两个位置，相减得到真实长度(这里还要-1，因为循环多走一次会多1)
     * 由于最后结果需要字符串，首先设置一个最终获取到的字符串的起终点，初始都为0，
     * 而每一次循环，中心的位置就会向后移动一个字符，此时如果所有字符都不形成回文，则起终点则一直+1
     * 而如果出现了一个长的回文字符串，则此时起终点就会比较长短，变成最长的回文字符串的起终点
     */
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
//            System.out.println("len1:" + len1);
            int len2 = expandAroundCenter(s, i, i + 1);
//            System.out.println("len2:" + len2);

            int len = Math.max(len1, len2);
            if (len > end - start) {
//                System.out.println("i:" + i + " len:" + len);
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
            System.out.println("start:" + start + " end:" + end);
        }

        return s.substring(start, end + 1);
    }

    private static int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        //注意，满足条件后还会再走一次循环，所以R-L-1就得到了回文字符串的真实长度
        return R - L - 1;
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("abcdzjudcba"));
    }
}
